package com.cat.dynamicPlanning;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-maximum-removals-from-source-string/
 * @create 2025/9/9 21:10
 * @since JDK17
 */

public class Solution98 {
    int n, m;
    int[][] dp;
    char[] s, p;
    HashSet<Integer> set = new HashSet<>();

    int dfs(int i, int j) {
        if (i < j) {
            return Integer.MIN_VALUE;
        }
        if (i < 0) {
            return 0;
        }
        if (dp[i][j + 1] != -1) {
            return dp[i][j + 1];
        }
        int res = dfs(i - 1, j) + (set.contains(i) ? 1 : 0);
        if (j >= 0 && s[i] == p[j]) {
            res = Math.max(res, dfs(i - 1, j - 1));
        }
        return dp[i][j + 1] = res;
    }

    public int maxRemovals(String source, String pattern, int[] targetIndices) {
        n = source.length();
        m = pattern.length();
        for (int num : targetIndices) {
            set.add(num);
        }
        dp = new int[n + 1][m + 1];
        s = source.toCharArray();
        p = pattern.toCharArray();
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(n - 1, m - 1);
    }
}
